HPAVC

home *** CD-ROM | disk | FTP | other *** search

/ HPAVC / HPAVC CD-ROM.iso / pc / TPTUTR0F.ZIP / PASCAL18.TXT < prev next >

Wrap

Text File | 1996-03-03 | 31.0 KB | 938 lines

Turbo Pascal for DOS Tutorial by Glenn Grotzinger Part 18: Chained or Linked lists, the linked list sort copyright(c) 1995-96 by Glenn Grotzinger Here is a solution from last time... {$M 64000,0,655360} program part17; uses crt; type arptr = ^atype; atype = array[1..15000] of integer; var a: arptr; number: integer; c, i, j, PIVOT, t: integer; found: boolean; location: integer; outfile: text; procedure quicksort(L, R: integer); { nothing to say we couldn't sort the data... } begin if wherex = 79 then begin gotoxy(1, wherey); clreol; end else write(#254); if L < R then begin i := L + 1; j := R; PIVOT := A^[L]; repeat while a^[i] <= PIVOT do inc(i); while a^[j] > PIVOT do dec(j); if i < j then begin t := A^[i]; A^[i] := a^[j]; A^[j] := t; end; until i > j; a^[l] := A^[j]; a^[j] := PIVOT; quicksort(L, j-1); quicksort(i, R); end; end; procedure bsearch(number, lowend, highend: integer; var found: boolean); var midpoint: integer; begin if lowend > highend then found := false else begin midpoint := (lowend + highend) div 2; if number = a^[midpoint] then begin found := true; location := midpoint; end else if number < a^[midpoint] then bsearch(number, lowend, midpoint-1, found) else if number > a^[midpoint] then bsearch(number, midpoint+1, highend, found); end; end; begin if maxavail - sizeof(a) > 0 then new(a) else begin writeln('Out of memory!'); halt(1); end; randomize; assign(outfile, 'LOCAT2.TXT'); rewrite(outfile); for c := 1 to 15000 do a^[c] := random(25000) + 1; quicksort(1, 15000); for c := 1 to 15000 do begin number := random(25000) + 1; bsearch(number, 1, 15000, found); if found then writeln(outfile, c, ') ', number, ' was found at position ', location, '.'); end; dispose(a); close(outfile); end. Here is the solution I got from part 10...No one tried it and sent it to me. Here's the UNIT. Keep in mind that I said to JUST CREATE ONE. You don't have to have the same functions that I had in there. Just as long as it works.... {$O+} unit unit10; interface type strtype = array[1..3] of string[80]; {$I COMPHVN.INC} function numeric(str: string): boolean; procedure writerecord(var outfile: file; strs: strtype); implementation function numeric(str: string): boolean; var num: boolean; i: integer; begin i := 1; num := true; while (num) and (i <= length(str)) do begin num := (str[i] in ['0'..'9','.',' ']); inc(i); end; numeric := num; end; procedure writerecord(var outfile: file; strs: strtype); var numerr: integer; writerec: comphvndata; begin with writerec do begin {part 1} datacode := copy(strs[1], 1, 7); acct_classification := strs[1][8]; val(copy(strs[1], 10, 3), phone_area, numerr); val(copy(strs[1], 13, 3), phone_prefix, numerr); val(copy(strs[1], 16, 4), phone_exchange, numerr); val(copy(strs[1], 20, 3), work_area, numerr); val(copy(strs[1], 23, 3), work_prefix, numerr); val(copy(strs[1], 26, 4), work_exchange, numerr); val(copy(strs[1], 30, 3), other_area, numerr); val(copy(strs[1], 33, 3), other_prefix, numerr); val(copy(strs[1], 36, 4), other_exchange, numerr); cnct1_lname := copy(strs[1], 40, 16); cnct1_fname := copy(strs[1], 56, 11); cnct1_minit := strs[1][67]; val(copy(strs[1], 68, 5), cnct1_pobox, numerr); cnct1_sname := copy(strs[1], 73, 8); {part2} accept_check := (strs[2][8] = 'Y'); cnct1_stype := copy(strs[2], 10, 4); val(copy(strs[2], 14, 4), cnct1_apt, numerr); cnct1_city := copy(strs[2], 18, 10); cnct1_state := copy(strs[2], 28, 2); val(copy(strs[2], 30, 9), cnct1_zip, numerr); val(copy(strs[2], 39, 2), cnct1_birthm, numerr); val(copy(strs[2], 41, 2), cnct1_birthd, numerr); val(copy(strs[2], 43, 4), cnct1_birthy, numerr); val(copy(strs[2], 47, 9), balnce_credt, numerr); val(copy(strs[2], 56, 8), total_sold, numerr); cnct1_emp_code := copy(strs[2], 64, 4); val(copy(strs[2], 68, 3), total_sales, numerr); emp_name := copy(strs[2], 71, 10); {part3} accept_credt := (strs[3][8] = 'Y'); val(copy(strs[3], 10, 4), emp_stnum, numerr); emp_sttype := copy(strs[3], 14, 4); emp_city := copy(strs[3], 18, 10); emp_state := copy(strs[3], 28, 2); val(copy(strs[3], 39, 3), emp_area, numerr); val(copy(strs[3], 42, 3), emp_prefix, numerr); val(copy(strs[3], 45, 4), emp_exchange, numerr); val(copy(strs[3], 49, 2), emp_yrs, numerr); compu := (strs[3][51] = 'Y'); compu_type := copy(strs[3], 52, 9); compu_mon := strs[3][61]; compu_cdr := (strs[3][62] = 'Y'); compu_cdt := strs[3][63]; val(copy(strs[3], 64, 2), compu_mem, numerr); minor := (strs[3][66] = 'Y'); end; blockwrite(outfile, writerec, sizeof(writerec)); end; end. And now here is the main program I got for part 10. What I can see that is not readily explainable here (I used every method I could think of that falls into the rules I outlined for the thing.). The two compiler directives you see below turn off stack checking and range checking respectively. With regards to data intensive applications such as sorting, large #'s of comparisons, and so forth, adding these speeds it up. {$S-} {$R-} program part10; uses dos, unit10, overlay; {$O UNIT10.TPU} var strs: strtype; outfile: file; infile, errfile: text; i: integer; errwritten: boolean; procedure writeerror(errline, errtype: string); var temp1: string; begin temp1 := copy(errline, 1, 20); writeln(errfile, temp1,'':10, errtype); errwritten := true; end; function checkstatus(strs: strtype): boolean; var check: boolean; seqs: array[1..3] of char; cnts: array[1..3] of byte; i: byte; errtype: string; begin check := true; for i := 1 to 3 do cnts[i] := 0; for i := 1 to 3 do begin seqs[i] := strs[i][9]; case seqs[i] of '1': inc(cnts[1]); '2': inc(cnts[2]); '3': inc(cnts[3]); end; end; for i := 1 to 3 do begin if cnts[i] = 0 then begin errtype := 'Missing line #' + chr(i+48); writeerror(strs[i], errtype); check := false; end; if cnts[i] = 2 then begin errtype := 'Duplicate line #' + chr(i+48); writeerror(strs[i], errtype); check := false; end; end; checkstatus := check; end; procedure checkdatacodes(strs: strtype); var datacodes: array[1..3] of string[7]; check1: string[5]; check2: char; error: string[20]; begin for i := 1 to 3 do datacodes[i] := copy(strs[i], 1, 7); check1 := copy(strs[1], 40, 5); check2 := strs[1][56]; for i := 1 to 3 do begin if datacodes[i][6] <> '*' then writeerror(strs[i], 'Invalid datacode.'); if (check1 <> copy(datacodes[i], 1, 5)) or (check2 <> datacodes[i][7]) then writeerror(strs[i], 'Datacode does not agree with name.'); end; end; procedure checknumeric(strs: strtype); var temp1, temp2: string; int, numerr, numdiff: integer; year, month, day, dayofweek: word; empyrs, birthy, bmo, bday: word; age: byte; isminor: boolean; begin if numeric(copy(strs[1], 10, 3)) = false then writeerror(strs[1], 'Phone-area is not numeric.'); if numeric(copy(strs[1], 13, 3)) = false then writeerror(strs[1], 'Phone-prefix is not numeric.'); if numeric(copy(strs[1], 16, 4)) = false then writeerror(strs[1], 'Phone-exchange is not numeric.'); if numeric(copy(strs[1], 20, 3)) = false then writeerror(strs[1], 'Work-area is not numeric.'); if numeric(copy(strs[1], 23, 3)) = false then writeerror(strs[1], 'Work-prefix is not numeric.'); if numeric(copy(strs[1], 26, 4)) = false then writeerror(strs[1], 'Work-exchange is not numeric.'); if numeric(copy(strs[1], 30, 3)) = false then writeerror(strs[1], 'Other-area is not numeric.'); if numeric(copy(strs[1], 33, 3)) = false then writeerror(strs[1], 'Other-prefix is not numeric.'); if numeric(copy(strs[1], 36, 4)) = false then writeerror(strs[1], 'Other-exchange is not numeric.'); if numeric(copy(strs[1], 68, 5)) = false then writeerror(strs[1], 'cnct1-pobox is not numeric.'); if numeric(copy(strs[3], 30, 9)) = false then writeerror(strs[3], 'emp-zip is not numeric.'); if numeric(copy(strs[3], 39, 3)) = false then writeerror(strs[3], 'emp-area is not numeric.'); if numeric(copy(strs[3], 42, 3)) = false then writeerror(strs[3], 'emp-prefix is not numeric.'); if numeric(copy(strs[3], 45, 4)) = false then writeerror(strs[3], 'emp-exchange is not numeric.'); temp2 := copy(strs[3], 49, 2); if numeric(temp2) = false then writeerror(strs[3], 'emp-yrs is not numeric.') else val(temp2, empyrs, numerr); if numeric(copy(strs[2], 30, 9)) = false then writeerror(strs[2], 'cnct1-zip is not numeric.'); temp2 := copy(strs[2], 39, 2); if numeric(temp2) = false then writeerror(strs[2], 'cnct1-birthm is not numeric.') else val(temp2, bmo, numerr); temp2 := copy(strs[2], 41, 2); if numeric(temp2) = false then writeerror(strs[2], 'cnct1-birthd is not numeric.') else val(temp2, bday, numerr); temp1 := copy(strs[2], 43, 4); if numeric(temp1) = false then writeerror(strs[2], 'cnct1-birthy is not numeric.') else begin val(temp1, int, numerr); if (int < 1900) or (int > 1999) then writeerror(strs[2], 'cnct1-birthy is not in this century.'); end; getdate(year, month, day, dayofweek); val(temp1, birthy, numerr); numdiff := year - birthy; if numdiff < empyrs then writeerror(strs[3], 'The emp-yrs doesn''t make sense.'); age := year - birthy; if month < bmo then dec(age); if month = bmo then if day < bday then dec(age); isminor := (age < 21); if ((isminor = true) and (strs[3][66] = 'N')) or ((isminor = false) and (strs[3][66] = 'Y')) then writeerror(strs[3], 'Minor is set incorrectly.'); if numeric(copy(strs[2], 47, 9)) = false then writeerror(strs[2], 'balance-credt is not numeric.'); if numeric(copy(strs[2], 56, 8)) = false then writeerror(strs[2], 'total-sold is not numeric.'); if numeric(copy(strs[2], 68, 3)) = false then writeerror(strs[2], 'total-sales is not numeric.'); if numeric(copy(strs[3], 64, 2)) = false then writeerror(strs[3], 'compu-mem is not numeric.'); end; procedure checkprefix(strs: strtype); begin if strs[1][13] in ['0'..'1'] then writeerror(strs[1], 'phone-prefix started with a 0 or 1.'); if strs[1][23] in ['0'..'1'] then writeerror(strs[1], 'work-prefix started with a 0 or 1.'); if strs[1][33] in ['0'..'1'] then writeerror(strs[1], 'other-prefix started with a 0 or 1.'); if strs[3][42] in ['0'..'1'] then writeerror(strs[3], 'emp-prefix started with a 0 or 1.'); end; procedure checkacct(strs: strtype); begin if strs[1][8] in ['B','C','G','P','O'] then else writeerror(strs[1], 'acct-classification is invalid.'); end; procedure checkyn(strs: strtype); begin if strs[2][8] in ['Y', 'N'] then else writeerror(strs[2], 'accept-check is invalid.'); if strs[3][8] in ['Y', 'N'] then else writeerror(strs[3], 'accept-credt is invalid.'); if strs[3][51] in ['Y', 'N'] then else writeerror(strs[3], 'compu is invalid.'); if strs[3][62] in ['Y', 'N'] then else writeerror(strs[3], 'compu-cdr is invalid.'); if strs[3][66] in ['Y', 'N'] then else writeerror(strs[3], 'minor is invalid.'); end; procedure checkcompun(strs: strtype); begin if strs[3][51] = 'N' then if (copy(strs[3], 52, 14) <> ' 0 ') then writeerror(strs[3], 'There were fields present when compu was N.'); end; procedure checkempcode(strs: strtype); begin if copy(strs[2], 64, 4) = 'RET ' then if (copy(strs[2], 71, 10) <> ' ') and (copy(strs[3], 10, 20) <> '0 ') and (copy(strs[3], 30, 20) <> '0 0 0 0 ') then writeerror(strs[3], 'empcodes are present when RET is true.'); end; procedure checkcompumon(strs: strtype); begin if strs[3][61] in ['S','V','E','C','H','I'] then else writeerror(strs[3], 'compu-mon is invalid.'); end; procedure checkcompucdt(strs:strtype); begin if strs[3][63] in ['1','2','4','6','8'] then else writeerror(strs[3], 'compu-cdt is invalid.'); end; procedure checksttype(strs: strtype); var a: string; begin a:=copy(strs[3], 14, 4); if (a <> 'BLVD') and (a <> 'LANE') and (a <> 'ST ') and (a <> 'AVE ') and (a <> 'CT ') and (a <> 'LOOP') and (a <> 'DR ') and (a <> 'CIRC') and (a <> 'RR ') then writeerror(strs[3], 'emp-sttype is invalid.'); a:=copy(strs[2], 10, 4); if (a <> 'BLVD') and (a <> 'LANE') and (a <> 'ST ') and (a <> 'AVE ') and (a <> 'CT ') and (a <> 'LOOP') and (a <> 'DR ') and (a <> 'CIRC') and (a <> 'RR ') then writeerror(strs[2], 'cnct1-stype is invalid.'); end; procedure writeheader; begin writeln(errfile, 'Error Report -- INDATA.TXT':50); writeln(errfile, '--------------------------':50); writeln(errfile); writeln(errfile, 'First 20 characters','':10, 'Problem'); writeln(errfile, '-------------------','':10, '-------'); end; begin ovrinit('PART10.OVR'); if ovrresult <> 0 then begin case ovrresult of -1: writeln('Overlay manager error.'); -2: writeln('Overlay file not found.'); -3: writeln('Not enough memory for overlay buffer.'); -4: writeln('Overlay I/O error.'); end; halt(1); end; ovrinitems; case ovrresult of 0: writeln('Overlay loaded to EMS memory!'); -5: writeln('No EMS driver found! Loading to conventional memory!'); -6: writeln('Not enough EMS memory to load! Loading to conventional', ' memory!'); end; assign(infile, 'INDATA.TXT'); reset(infile); assign(errfile, 'ERRORS.LOG'); rewrite(errfile); assign(outfile, 'COMPHVN.DAT'); rewrite(outfile, 1); writeheader; while not eof(infile) do begin errwritten := false; for i := 1 to 3 do readln(infile, strs[i]); if checkstatus(strs) then begin checkdatacodes(strs); checknumeric(strs); checkprefix(strs); checkacct(strs); checkyn(strs); checkempcode(strs); checkcompun(strs); checkcompumon(strs); checkcompucdt(strs); checksttype(strs); end; if errwritten = false then writerecord(outfile, strs); end; close(infile); close(errfile); close(outfile); end. Now we will discuss the idea of the linked list or chained list. Basically, there are 4 types of linked lists that we can discuss, the singularly linked linear list (SLLL), singularly linked circular list (SLCL), doubly linked linear list (DLLL), and the doubly linked circular list (DLCL). I will use the abbreviations I placed in the parentheses for any future references to these data types. These are basically the preferred ways to allocate large amounts of storage space on the heap. All linked lists are basically describable in the best analogy as a chain. They are record structures which have pointers that interconnect them. The method that these structures are connected distinguish the type of linked list it is. We will look at an example of the use of SLLL's, observe the advantages of linked lists through what we do with the example, and study the things to look out for on all 4 types. SLLL Concepts ============= This is the simplest type, in sense. It involves a record structure which is connected in a chain in a linear fashion with one link forward to the next link. A sample record structure for an SLLL follows below. type nodeptr = ^node; nodetype = record ourinfo: integer; nextnode: nodeptr; end; An example of an SLLL conceptually is something like this: NODE-->NODE-->NODE-->NODE-->NODE-->NODE-->NODE-->nil As we remember from earlier, nil is what we set a pointer to, if we do not want it to point to anything...In the use of an SLLL, it is also what we will use to indicate whether we are at the end of the list or not. We will see from the slll_demo program that there are several specialized issues we need to take into consideration with working with any linked or chained list. 1) We need to make a special case to insert or delete a node from the start of the list. 2) We need to be sure to maintain nil pointers in any insert or delete operation. 3) NEVER NEVER NEVER WORK DIRECTLY WITH THE HEAD TRACKING POINTER WE ORIGINALLY ALLOCATE UNLESS WE DESIGN OUR CODE COMPLETELY AROUND RECURSION. As a result, you will cause what is called a heap leak. This is where the pointer loses track of where the data it points to is stored. Logically, looking at the model above, if we disconnect one of the pointers, represented by the arrows, we lose track of the rest of the list, or chain. Work with a temporary pointer for each linked list function. What I say by recursion, you will see later in this document. 4) With regards to the example I wrote, I tried to demonstrate any and all functions that we might need with an SLLL. 5) Pointers that point at nil CAN NOT be deallocated. You will see this fact manifest itself by the memory statement at the end being 8 bytes smaller than it was at the start. SLLLs Demonstrated ================== Here is the SLLL_DEMO program. I will place stop notes in there, as well as comments. Advantages of linked lists: We will see here, that the data is not static, we can place data independently at different positions WITHOUT shuffling data, remove data in the same fashion, and definitely are capable of handling *A LOT* more data than 64KB, since we only have a 4 byte stub in that area. Take a good look at this program and seek to understand EXACTLY how it works. As you will remember from last time, a direct assignment to a pointer is making it point to something while a reference to the pointer (via ^) changes the contents of the data it points to. I recommend you draw out what is going on via pencil and paper, using boxes to represent the records and arrows representing pointers. It will help you VASTLY to do this in understanding what is going on. Remember a pointer can only point to one thing at a time. When you look at this program, seek to answer the following questions taking any "housekeeping functions" out of consideration: 1) Why is the insert code different than the build code? 2) Why is the delete code different than the cleanup code? 3) On the "divisible by 8" search, why is the NEXT node being searched for this and not the current node? 4) Why did I say to always use a temporary variable? Or Why does the statement p := list; always occur? 5) Observe methods of moving through the list. program slll_demo; uses crt; { Program written by Glenn Grotzinger for a demonstration of all of the functions/uses of a linked list that the author could think of. the variable used throughout called p, and sometimes t, are temporary variables. Note: This probably isn't completely optimized. } type nodeptr = ^nodetype; nodetype = record thenum: integer; nextnode: nodeptr; end; var list: nodeptr; procedure buildlist(var list: nodeptr); { This procedure builds up the list for us. } var p: nodeptr; i: integer; begin new(list); { This is creating the head of the list } list^.thenum := 1; p := list; { Set and move temporary pointer } for i := 2 to 18 do begin new(p^.nextnode); p^.nextnode^.thenum := i; p := p^.nextnode; { p := p^.nextnode advances the temporary pointer to the next node. this is a memory storage address or pointer and not a direct variable, referencing a node of the linked list. Anything, in reality does not become a pointer until the new function is used. } end; p^.nextnode := nil; { set last pointer to nothing } end; procedure writelist(list: nodeptr); { This procedure serves the function of writing out the list for us to the screen when called } var p: nodeptr; begin p := list; while p <> nil do { while we're not at the end of the list } begin write(p^.thenum:3); p := p^.nextnode; end; end; procedure insert(var list: nodeptr); { This procedure will serve to insert a node into the list either in the middle or the end. The logic can be done for the head of the list. } var p: nodeptr; begin new(p); p^.thenum := 20; p^.nextnode := list; if p^.nextnode = nil then { maintenance of the end of list marker } p^.nextnode^.nextnode := nil; list := p; end; procedure delete(var list: nodeptr); { This is a procedure that will serve to delete a node from the list, and consequently deallocate the memory. It is possible to remove the node without deallocating the memory, though it is a bad practice to do so } var p, t: nodeptr; begin p := list; t := p^.nextnode^.nextnode; dispose(p^.nextnode); p^.nextnode := t; end; procedure insertbythree(var list: nodeptr); { This procedure moves through the linked list and determines where the new nodes needs to be inserted, then calls the insert function written before } var p: nodeptr; i: integer; begin p := list; i := 1; while p <> nil do begin p := p^.nextnode; inc(i); if i mod 3 = 0 then insert(p^.nextnode); end; end; procedure findanddispose(var list: nodeptr); { This procedure finds and disposes the first number in the list divisible by 8. } var p, t: nodeptr; begin p := list; while (p^.nextnode <> nil) and (p^.nextnode^.thenum mod 8 <> 0) do p := p^.nextnode; delete(p); end; procedure cleanup(var list: nodeptr); { This procedure removes the list from memory. } var p, t: nodeptr; begin p := list; while p <> nil do begin t := p^.nextnode; dispose(p); p := t; end; end; begin clrscr; writeln;writeln; writeln('Free memory available: ', memavail, ' bytes.'); buildlist(list); writeln('Free memory available: ', memavail, ' bytes.'); write('The list is: '); writelist(list); writeln;writeln; writeln('Now we will insert a 20 in every third position'); insertbythree(list); writeln('Free memory available: ', memavail, ' bytes.'); write('The list is: '); writelist(list); writeln;writeln; write('Now we will search for and take the first # divisible by 8 '); writeln('out of the list.'); findanddispose(list); writeln('Free memory available: ', memavail, ' bytes.'); write('The list is: '); writelist(list); writeln;writeln; writeln('Now we will be good little programmers and clean up our list. :)'); cleanup(list); writeln('Free memory available: ', memavail, ' bytes.'); end. Hopefully, you can go through here, and follow the logic (actually, you will need to do that successfully to understand what is going on). Linked lists are very modular in nature. Therefore, a good understanding of what is going on here is essential. As a proof to be able to think through the logic of using pointers in linked structures, write out and logically explain on your sheet of paper how to perform the following (I will not provide a solution for this one -- code it up yourself and try and figure it out -- this is an important skill you will need to start developing as a programmer at this point, since you're at a pretty advanced level now (:))), and then code it up as a program: 1) Create 1000 nodes in an SLLL that consists of integers numbered from 1 to 1000. 2) Print this list to a text file. 3) Reverse the direction of the linked list. By doing this, I mean, instead of the linked list looking like this conceptually: NODE-->NODE-->NODE-->nil make it look like this: nil<--NODE<--NODE<--NODE DO NOT CREATE ANOTHER LINKED LIST IN MEMORY. USE THE CURRENT ONE YOU HAVE BUILT. 4) Print the new list to the same text file. Instead of it being from 1 to 1000 as the first printing was, it should be from 1000 to 1. CLUE: Think about how many temporary variables you will need (1? Maybe 2?, Possibly 3?). SLCL Concepts ============= This is essentially the same as an SLLL, except instead of being nil at the end of the list, the end of the list points at the beginning of the list. This type uses the same record format as the SLLL. Conceptually, an SLCL looks like this: NODE--->NODE--->NODE--->NODE--->NODE ^ | | V NODE NODE ^ | | V NODE<---NODE<---NODE<---NODE<---NODE As before with the SLLL, one of these nodes would be denoted as the head of the list. The only consideration that would differ that I could note, is that you would use a comparison of your temporary pointer with your head pointer in order to move through the list. So instead of while p <> nil, it would be while p <> list in the above example to make it that way. DLLL Concepts ============= This type of linked list uses a different kind of record format. It looks like this: type nodeptr = ^node; node = record ourinfo: integer; lastnode, nextnode: nodeptr; end; Conceptually, a DLLL looks like this: nil <-- <-- <-- <-- NODE NODE NODE NODE --> --> --> --> nil If you study up your logic from previously, this one shouldn't be too awfully bad to figure out. DLCL Concepts ============= This type of list uses the same record format as the DLLL. The conceptual diagram looks much like the SLCL diagram, but with double links much like the DLLL diagram, instead of single links. Final Thoughts on Linked Lists ============================== I did not provide examples of SLCLs, DLLLs, and DLCLs , merely for space, and also by the fact that I have never had reason to use the other three types. I am presenting their basics here, merely for people's study, and learning. Using the knowledge learned from doing those logic problems presented in the SLLLs, and references (though I find those to be VERY sparse on the types other than SLLL), you should be able to come up with the code to do the other three types pretty readily. Always remember that the best thing to do to work out the logic of what to do with the pointers is to draw it out using the boxes and the arrows. An Idea on Sorting Data Using Linked Lists ========================================== Here, I will now present the reasoning behind my "recursion" statement, plus an idea of sorting data upon build. I don't have any stats on this being more or less efficient than using one of the array sorts, but if you can't use an array to sort in memory, you would have to resort to this. Here is a little code/pseudocode (with a bent toward sorting names alphabetically) For purposes of the recursion, we will call the function INSERT: IF WE ARE TO PUT NODE HERE GET DATA TO PUT INTO NODE (read data from file, or elsewhere) WHILE DATA IS NOT DONE DO BEGIN IF NIL LIST THEN PUT NODE HERE ELSE PUT NODE HERE = NEWNAME <= NODE^.NAME IF WE ARE TO PUT NODE HERE THEN BEGIN new(p); SET DATA TO NODE p^.nextnode := LIST; if p^.nextnode = nil then p^.nextnode^.nextnode = nil; list := p; END ELSE INSERT(LIST^.NEXTNODE); IF WE ARE TO PUT NODE HERE THEN BEGIN GET INFO. DO NOT PUT NODE HERE (boolean variable set to false). END. END. This general code does work for a high capacity. I have used this code to sort a maximum of an 86KB list of 150 char items per line alphabetically using memory alone, no disk swapping. For practice: Do things as I have suggested throughout this document. No real practice problem. Next Time ========= We will talk about binary trees. Be sure to send comments to ggrotz@2sprint.net. I will say again that I apologize for the long period of time it took to get this out. I also apologize for the length this document has become. Be sure to please comment on how this part is.